The present invention relates to methods and apparatus for scheduling, and in particular, to methods and apparatus for scheduling composite workloads comprising related workflows in order to maximize business value across all the related workflows.
Response time of an electronic commerce website in completion of requested transactions is a key aspect of user satisfaction of the service offered by the electronic commerce website. Therefore, it is advantageous for the operator of the electronic commerce website to provide methods and apparatus to provide expedient response time to web service request.
A typical web service request to an electronic commerce web site may be decomposable into related workflows of web services that can then be individually executed. For example, a travel arrangement request may be decomposed into a airlines ticket purchase workflow, a hotel room selection workflow and a car rental workflow. In turn, the workflows themselves may be further decomposable into a series of business steps. For example, an electronic purchase workflow may be comprised of a first business step to authenticate a user, a second business step to authenticate the credit card entered by the user by communicating with a credit card authentication server, a third business step to collect information regarding the purchase amount from an electronic merchant, a fourth business step to perform a check on availability of sufficient credit, a fifth business step to confirm the transaction, and so on. Each workflow can be thought of as a user of a variety of web services. The web services desired by a workflow may in turn be offered by more than one web service providers, For example, in the electronic purchase workflow example given above, a credit card server may offer card authentication service and an electronic commerce server may offer purchase service, etc.
To meet the objective of expedient response to user requests, prior art electronic commerce web sites use such decomposition of user request into business processes to allocate the business process tasks to service providers. The service providers also offer quantified quality of service measurements on the services offered. For example, service providers advertise a guaranteed turnaround time for business process execution.
One prior art approach is to assign all requests for a particular type of service to the provider with the best guaranteed turnaround time. However, this approach can lead to performance degradation due to its servers becoming overloaded.
In the context of service assignment and scheduling, the publication authored by Zeng. L. et al. (2003), “Quality Driven Web Services Composition”, In Proc. of WWW (hereafter “Zeng”), maps web service calls to potential servers, but Zeng does not address optimizing aggregate business values across workflows by assigning business processes to a plurality of service providers.
The publication authored by Urgaonkar, B. et al. (2005), “Dynamic Provisioning of Multi-Tier Internet Applications,” (hereafter “Urgaonkar”) presents a dynamic provisioning approach that uses both predictive and reactive techniques for multi-tiered Internet application delivery, but Urgaonkar does not describe how to optimize aggregate business values across workflows by assigning business processes to a plurality of service providers in view of alternate query execution plans and replicated data sources.
Therefore, there is a need for an improved method and apparatus for scheduling of business processes based on the service type used so that the scheduling process maximizes a desired business value totaled across all the workflows related to the requests.